package william.hash;

import java.util.*;

/**
 * @author ZhangShenao
 * @date 2024/3/5
 * @description <a href="https://leetcode.cn/problems/sort-characters-by-frequency/description/">...</a>
 */
public class Leetcode451_根据字符出现频率排序 {
    /**
     * 借助Map实现
     * 使用Map维护一个词频表,保存字符串中每个字符的词频
     * 遍历字符串,更新词频表
     * 使用一个List保存所有字符,并对List进行排序,排序规则是词频降序
     * 遍历List,拼接字符串
     * <p>
     * 时间复杂度O(N) 需要遍历一次字符串
     * 空间复杂度O(N) 需要额外申请一个Map和一个List,长度均为字符串长度
     */
    public String frequencySort(String s) {
        //边界条件校验
        if (s == null || s.isEmpty()) {
            return s;
        }

        //使用Map维护一个词频表,保存字符串中每个字符的词频
        int N = s.length();
        Map<Character, Integer> frequency = new HashMap<>(N);

        //遍历字符串,更新词频表
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int f = frequency.getOrDefault(c, 0);
            frequency.put(c, f + 1);
        }

        //使用一个List保存所有字符
        List<Character> chars = new ArrayList<>(frequency.keySet());

        //对List进行排序,排序规则是词频降序
        chars.sort((c1, c2) -> (frequency.get(c2) - frequency.get(c1)));


        //遍历词频表,拼接字符串
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < chars.size(); i++) {
            char c = chars.get(i);
            int f = frequency.get(c);
            for (int j = 0; j < f; j++) {
                result.append(c);
            }
        }

        //返回结果
        return result.toString();

    }

    public static void main(String[] args) {
        Leetcode451_根据字符出现频率排序 s = new Leetcode451_根据字符出现频率排序();
        String result = s.frequencySort("tree");
        System.out.println(result);
    }
}
